import java.util.Arrays;

/**
 * 面试题 08.11. 硬币
 * https://leetcode-cn.com/problems/coin-lcci/
 */
public class Solutions_mianshi_08_11 {
    public static void main(String[] args) {
//        int n = 5;  // output: 2  {5=5, 5=1+1+1+1+1}
        int n = 10;  // output: 4  {10=10, 10=5+5, 10=5+1+1+1+1+1, 10=1+1+1+1+1+1+1+1+1+1}

        int result = waysToChange(n);
        System.out.println(result);
    }

//    private static int[] coins = {1, 5, 10, 25};
    private static int[] coins = {5, 10, 25};
    private static int mod = 1_000_000_007;

    /**
     * 动态规划，从小币值到大币值遍历，积累每个硬币可以组成的方式数量
     */
    public static int waysToChange(int n) {
        int[] dp = new int[n + 1];
        // 每个硬币都可以使用币值为 1 的硬币来组成
        Arrays.fill(dp, 1);

        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                // i = 6，coin = 5 时，可以组成的方式数量为：通过币值 1 组成的方式 + 硬币(6 - 5 = 1)时能够组成的方式数量，
                // 因为硬币 1 加币值 5 可以得到硬币 6
                dp[i] = (dp[i] + dp[i - coin]) % mod;
            }
        }
        return dp[n];
    }
}
